SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Coupled pattern learner</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Coupled pattern learner</span></span>

</h1>

</header>

<p><b>Coupled Pattern Learner</b> (CPL) is a <a href="Machine_learning" title="Machine learning">machine learning</a> algorithm which couples the <a href="Semi-supervised_learning" class="mw-redirect" title="Semi-supervised learning">semi-supervised learning</a> of categories and relations to forestall the problem of semantic drift associated with boot-strap learning methods.

</p>

<div class="mw-heading mw-heading2"><h2 id="Coupled_Pattern_Learner">Coupled Pattern Learner</h2></div>

<p><a href="Semi-supervised_learning" class="mw-redirect" title="Semi-supervised learning">Semi-supervised learning</a> approaches using a small number of labeled examples with many unlabeled examples are usually unreliable as they produce an internally consistent, but incorrect set of extractions. CPL solves this problem by simultaneously learning classifiers for many different categories and relations in the presence of an <a href="Ontology_(information_science)" title="Ontology (information science)">ontology</a> defining constraints that couple the training of these classifiers. It was introduced by Andrew Carlson, Justin Betteridge, Estevam R. Hruschka Jr. and Tom M. Mitchell in 2009.<sup id="cite_ref-cbl2009_1-0" class="reference"><a href="#cite_note-cbl2009-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-cpl2010_2-0" class="reference"><a href="#cite_note-cpl2010-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="CPL_overview">CPL overview</h2></div>

<p>CPL is an approach to <a href="Semi-supervised_learning" class="mw-redirect" title="Semi-supervised learning">semi-supervised learning</a> that yields more accurate results by coupling the training of many information extractors. Basic idea behind CPL is that semi-supervised training of a single type of extractor such as ‘coach’ is much more difficult than simultaneously training many extractors that cover a variety of inter-related entity and relation types. Using prior knowledge about the relationships between these different entities and relations CPL makes unlabeled data as a useful constraint during training. For e.g., ‘coach(x)’ implies ‘person(x)’ and ‘not sport(x)’.

</p>

<div class="mw-heading mw-heading2"><h2 id="CPL_description">CPL description</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Coupling_of_predicates">Coupling of predicates</h3></div>

<p>CPL primarily relies on the notion of coupling the <a href="Learning" title="Learning">learning</a> of multiple functions so as to constrain the semi-supervised learning problem. CPL constrains the learned function in two ways.

</p>

<ol><li>Sharing among same-arity predicates according to logical relations</li>

<li>Relation argument type-checking</li></ol>

<div class="mw-heading mw-heading3"><h3 id="Sharing_among_same-arity_predicates">Sharing among same-arity predicates</h3></div>

<p>Each predicate P in the ontology has a list of other same-arity predicates with which P is mutually exclusive. If A is <a href="Mutually_exclusive" class="mw-redirect" title="Mutually exclusive">mutually exclusive</a> with predicate B, A’s positive instances and patterns become negative instances and negative patterns for B. For example, if ‘city’, having an instance ‘Boston’ and a pattern ‘mayor of arg1’, is mutually exclusive with ‘scientist’, then ‘Boston’ and ‘mayor of arg1’ will become a negative instance and a negative pattern respectively for ‘scientist.’ Further, Some categories are declared to be a subset of another category. For e.g., ‘athlete’ is a subset of ‘person’.

</p>

<div class="mw-heading mw-heading3"><h3 id="Relation_argument_type-checking">Relation argument type-checking</h3></div>

<p>This is a type checking information used to couple the learning of relations and categories. For example, the arguments of the ‘ceoOf’ relation are declared to be of the categories ‘person’ and ‘company’. CPL does not promote a pair of noun phrases as an instance of a relation unless the two noun phrases are classified as belonging to the correct argument types.

</p>

<div class="mw-heading mw-heading3"><h3 id="Algorithm_description">Algorithm description</h3></div>

<p>Following is a quick summary of the CPL algorithm.<sup id="cite_ref-cpl2010_2-1" class="reference"><a href="#cite_note-cpl2010-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<pre>Input: An ontology O, and a text corpus C

Output: Trusted instances/patterns for each predicate

<b>foreach</b> predicate p in O <b>do</b>

EXTRACT candidate instances/contextual patterns using recently promoted patterns/instances;

FILTER candidates that violate coupling;

RANK candidate instances/patterns;

PROMOTE top candidates;

</pre>

<div class="mw-heading mw-heading4"><h4 id="Inputs">Inputs</h4></div>

<p>A large <a href="Text_corpus" title="Text corpus">corpus</a> of Part-Of-Speech tagged sentences and an initial ontology with predefined categories, relations, mutually exclusive relationships between same-arity predicates, subset relationships between some categories, seed instances for all predicates, and seed patterns for the categories.

</p>

<div class="mw-heading mw-heading4"><h4 id="Candidate_extraction">Candidate extraction</h4></div>

<p>CPL finds new candidate instances by using newly promoted patterns to extract the noun phrases that co-occur with those patterns in the text corpus. CPL extracts,

</p>

<ul><li>Category Instances</li>

<li>Category Patterns</li>

<li>Relation Instances</li>

<li>Relation Patterns</li></ul>

<div class="mw-heading mw-heading4"><h4 id="Candidate_filtering">Candidate filtering</h4></div>

<p>Candidate instances and patterns are filtered to maintain high precision, and to avoid extremely specific patterns. An instance is only considered for assessment if it co-occurs with at least two promoted patterns in the text corpus, and if its co-occurrence count with all promoted patterns is at least three times greater than its co-occurrence count with negative patterns.

</p>

<div class="mw-heading mw-heading4"><h4 id="Candidate_ranking">Candidate ranking</h4></div>

<p>CPL ranks candidate instances using the number of promoted patterns that they co-occur with so that candidates that occur with more patterns are ranked higher. Patterns are ranked using an estimate of the precision of each pattern.

</p>

<div class="mw-heading mw-heading4"><h4 id="Candidate_promotion">Candidate promotion</h4></div>

<p>CPL ranks the candidates according to their assessment scores and promotes at most 100 instances and 5 patterns for each predicate. Instances and patterns are only promoted if they co-occur with at least two promoted patterns or instances, respectively.

</p>

<div class="mw-heading mw-heading2"><h2 id="Meta-Bootstrap_Learner">Meta-Bootstrap Learner</h2></div>

<p>Meta-Bootstrap Learner (MBL) was also proposed by the authors of CPL.<sup id="cite_ref-cpl2010_2-2" class="reference"><a href="#cite_note-cpl2010-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Meta-Bootstrap learner couples the training of multiple extraction techniques with a multi-view constraint, which requires the extractors to agree. It makes addition of coupling constraints on top of existing extraction algorithms, while treating them as black boxes, feasible. MBL assumes that the errors made by different extraction techniques are independent. Following is a quick summary of MBL.

</p>

<pre><b>Input</b>: An ontology O, a set of extractors ε

<b>Output</b>: Trusted instances for each predicate

<b>foreach</b> predicate p in O <b>do</b>

<b>foreach</b> extractor e in ε <b>do</b>

Extract new candidates for p using e with recently promoted instances;

FILTER candidates that violate mutual-exclusion or type-checking constraints;

PROMOTE candidates that were extracted by all extractors;

</pre>

<p>Subordinate algorithms used with MBL do not promote any instance on their own, they report the evidence about each candidate to MBL and MBL is responsible for promoting instances.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>In their paper <sup id="cite_ref-cbl2009_1-1" class="reference"><a href="#cite_note-cbl2009-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> authors have presented results showing the potential of CPL to contribute new facts to existing repository of semantic knowledge, Freebase <sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Co-training" title="Co-training">Co-training</a></li>

<li><a href="Never-Ending_Language_Learning" title="Never-Ending Language Learning">Never-Ending Language Learning</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCarlsonJustin_BetteridgeEstevam_R._Hruschka_Jr.Tom_M._Mitchell2009" class="citation journal cs1">Carlson, Andrew; Justin Betteridge; Estevam R. Hruschka Jr.; Tom M. Mitchell (2009). <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=1621829.1621830">"Coupling semi-supervised learning of categories and relations"</a>. <i>Proceedings of the NAACL HLT 2009 Workshop on Semi-Supervised Learning for Natural Language Processing</i>. Colorado, USA: Association for Computational Linguistics: <span class="nowrap">1–</span>9. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781932432381</bdi>.</cite></span>

</li>

<li id="cite_note-cpl2010-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-cpl2010_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-cpl2010_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-cpl2010_2-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFCarlsonJustin_BetteridgeRichard_C._WangEstevam_R._Hruschka_Jr.2010" class="citation book cs1">Carlson, Andrew; Justin Betteridge; Richard C. Wang; Estevam R. Hruschka Jr.; Tom M. Mitchell (2010). "Coupled semi-supervised learning for information extraction". <i>Proceedings of the third ACM international conference on Web search and data mining</i>. NY, USA: ACM. pp. <span class="nowrap">101–</span>110. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1718487.1718501">10.1145/1718487.1718501</a></span>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781605588896</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation journal cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20111206102101/http://download.freebase.com/datadumps/">"Freebase data dumps"</a>. Metaweb Technologies. 2009. Archived from <a rel="nofollow" class="external text" href="http://download.freebase.com/datadumps/">the original</a> on December 6, 2011.</cite> <span class="cs1-visible-error citation-comment"><code class="cs1-code">{{cite journal}}</code>: </span><span class="cs1-visible-error citation-comment">Cite journal requires <code class="cs1-code">|journal=</code> (help)</span></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFLiuXuejun_LiaoLawrence_Carin2008" class="citation journal cs1">Liu, Qiuhua; Xuejun Liao; Lawrence Carin (2008). "Semi-supervised multitask learning". <i>NIPS</i>.</cite></li>

<li><cite id="CITEREFShinyamaSatoshi_Sekine2006" class="citation journal cs1">Shinyama, Yusuke; Satoshi Sekine (2006). "Preemptive information extraction using unrestricted relation discovery". <i>HLT-Naacl</i>.</cite></li>

<li><cite id="CITEREFChangLev-Arie_RatinovDan_Roth2007" class="citation journal cs1">Chang, Ming-Wei; Lev-Arie Ratinov; Dan Roth (2007). "Guiding semi-supervision with constraint driven learning". <i>ACL</i>.</cite></li>

<li><cite id="CITEREFBankoMichael_J._CafarellaStephen_SoderlandMatt_Broadhead2007" class="citation journal cs1">Banko, Michele; Michael J. Cafarella; Stephen Soderland; Matt Broadhead; <a href="Oren_Etzioni" title="Oren Etzioni">Oren Etzioni</a> (2007). "Open information extraction from the web". <i>IJCAI</i>.</cite></li>

<li><cite id="CITEREFBlumTom_Mitchell1998" class="citation book cs1">Blum, Avrim; Tom Mitchell (1998). "Combining labeled and unlabeled data with co-training". <i>Proceedings of the eleventh annual conference on Computational learning theory</i>. pp. <span class="nowrap">92–</span>100. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F279943.279962">10.1145/279943.279962</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1581130570</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207228399">207228399</a>.</cite></li>

<li><cite id="CITEREFRiloffRosie_Jones1999" class="citation journal cs1">Riloff, Ellen; Rosie Jones (1999). "Learning dictionaries for information extraction by multi-level bootstrapping". <i>AAAI</i>.</cite></li>

<li><cite id="CITEREFRosenfeldRonen_Feldman2007" class="citation journal cs1">Rosenfeld, Benjamin; Ronen Feldman (2007). "Using corpus statistics on entities to improve semi-supervised relation extraction from the web". <i>ACL</i>.</cite></li>

<li><cite id="CITEREFWangWilliam_W._Cohen2008" class="citation journal cs1">Wang, Richard C.; William W. Cohen (2008). "Iterative set expansion of named entities using the web". <i>ICDM</i>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-26" href="https://en.wikipedia.org/wiki/?title=Coupled_pattern_learner&oldid=1297433480">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>